Dense meshes of interconnected data points are used to represent surfaces of arbitrary topology in numerous applications. For example, such meshes routinely result from three-dimensional data acquisition techniques such as laser range scanning and magnetic resonance volumetric imaging. These meshes are often configured in the form of a large number of triangles, and typically have an irregular connectivity, i.e., the vertices of the mesh have different numbers of incident triangles. Because of their complex structure and potentially tremendous size, dense meshes of irregular connectivity are difficult to handle in such common processing tasks as storage, display, editing, and transmission.
It is known that multiresolution representations of dense meshes can be used to facilitate these processing tasks. One approach to constructing multiresolution representations extends classical multiresolution analysis and subdivision techniques to arbitrary topology surfaces, as described in, for example, M. Lounsbery et al., "Multiresolution analysis for surfaces of arbitrary topological type," Transactions on Graphics 16:1, pp. 34-73, January 1997, and D. Zorin et al., "Interpolating subdivision for meshes with arbitrary topology," in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 189-192, 1996. Another more general approach is based on sequential mesh simplification, e.g., progressive meshes (PM), as described in, for example, H. Hoppe, "Progressive meshes," in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 99-108, 1996. Additional mesh simplification techniques are described in P. S. Heckbert and M. Garland, "Survey of polygonal surface simplification algorithms," Tech. rep., Carnegie Mellon University, 1997.
In both classical multiresolution analysis and mesh simplification, the basic objective is generally to represent meshes in an efficient and flexible manner, and to use this representation in algorithms which address the processing challenges mentioned above. An important element in the design of such algorithms is the construction of "parameterizations," i.e., functions mapping points on a coarse "base domain" mesh to points on a finer original mesh. Once a surface is characterized in this manner, as a function between a base domain and a space of three or more dimensions, many techniques from fields such as approximation theory, signal processing, and numerical analysis may be used to process data representing the surface.
A conventional approach to building parameterizations for meshes representing surfaces of arbitrary topology is based on approximation of a set of samples, as described in, for example, V. Krishnamurthy and M. Levoy, "Fitting smooth surfaces to dense polygon meshes," in Computer Graphics, (SIGGRAPH '96 Proceedings), pp. 313-324, 1996. A significant drawback of this type of approach is that the number of triangles in the base domain depends heavily on the geometric complexity of the surface to be characterized. Another problem is that the user may be required to define the entire base domain rather than only selected features. Additionally, in conventional remeshing techniques that work from coarse to fine mesh levels, it is possible for the procedure to "latch" onto the wrong surface in regions of high curvature.
Another conventional approach to building parameterizations for surfaces of arbitrary topology is based on remeshing an existing mesh with the goal of applying classical multiresolution analysis. A technique implementing this approach is described in M. Eck et al., "Multiresolution analysis of arbitrary meshes," in Computer Graphics (SIGGRAPH '95 Proceedings), pp. 173-182, 1995. A problem with algorithms of this type is that processing run times can be long because a large number of harmonic map computations are involved. Although this problem can be alleviated by reducing the harmonic map computations through hierarchical preconditioning, other problems remain. For example, there is generally no explicit control over the number of triangles in the base domain or the placement of boundaries. In addition, these and other remeshing algorithms typically generate only uniformly subdivided meshes which are subsequently made sparser through wavelet thresholding methods. Many extra subdivided levels may be needed to resolve one small local feature, and each additional level approximately quadruples the amount of computation and storage required to process the resulting mesh. This can lead to the intermediate construction of many more triangles than were contained in the original mesh, which unduly complicates the mesh processing operations.